// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 通过诱导排序（SAIS）构造后缀数组。
// 参见葛农、张森和陈伟红，
// “线性时间后缀数组构造的两种有效算法”，
// 特别是第3节(https:
// 另见http:
// 
// 受Yuta Mori的sais lite启发进行了优化
// (https:
// 
// 以及其他新的优化。

// 这些函数中的许多函数都是由其操作的类型的大小参数化的。generator gen.go制作
// 这些函数的副本，以便与其他尺寸的函数一起使用。
// 特别是：
// 
// -名称以_8_32结尾的函数采用[]字节和[]int32参数
// 并复制为_32_32、_8_64和_64_64形式。
// 后缀32_32和64_64_32和64_64缩短为普通的32和64。
// 函数体中包含文本“仅字节”或“256”的任何行
// 在创建_32_32和_64_64表单时将被剥离。
// （这些行通常是特定于8位的优化）
// 
// -名称以_32结尾的函数在[]int32 
// 上运行，并复制为_64形式。（请注意，它可能仍然需要[]字节，
// 但不需要将[]字节
// 扩展为完整整数数组的函数版本。）

// 此代码的整个运行时在输入大小上是线性的：
// 它运行一系列线性过程，将问题简化为
// 一个子问题，最大为一半，递归调用自身，
// 然后运行一系列线性过程，将子问题的答案
// 转换为原始问题的答案。
// 这给出了T（N）=O（N）+T（N/2）=O（N）+O（N/2）+O（N/4）+O（N）。
// 
// 通过调用O（N）大小的数组，代码的大纲是：
// 
// sais_I_N 
// placeLMS_I_B 
// bucketMax I_B 
// frequency_I_I_B 
// /<scan+freq>（2）
// /<scan-text，random bucket>（3）
// induceSubL\u I\u B 
// bucketMin\u I\u B 
// freq\u I\u B 
// INDUCTSUB 
// BACKETMAX 
// FREQUE IèB 
// /<scan+text，经常优化掉>（7）
// /<scan+FREQUE>（8）
// map_B 
// <scan-sa>（11）
// recurse_B 
// （递归调用sais_B_B以获取最多1/2输入的子问题，通常更小）
// unmap_I_B 
// expand_I_B 
// bucketMax_I_B 
// freq_I_B 
// /<scan+text，经常优化掉>（14）
// /<scan+freq>（15）
// INDUCTL\u B 
// BACKETMIN\u I\u B 
// freq\u I\u B 
// /<scan+text，经常优化掉>（17）
// /<scan+freq>（18）
// INDUCTS\u B 
// BACKETMAX\u I\u B 
// FREQUE\u I\u B 
// <scan+text，经常优化掉>（20）
// 
// 大纲显示，对于给定的递归级别，通常有22次扫描通过
// O（N）大小的数组。
// 在顶层，对8位输入文本进行操作，
// 六次频率扫描的大小是固定的（256）而不是潜在的
// 输入大小。此外，频率计数一次并缓存
// 只要有空间就可以这样做（通常几乎总是有空间，
// 并且总是在顶层有空间），这就消除了除
// 之外的所有频率文本扫描（即6次扫描中的5次）。
// 因此递归的顶层只执行22-6-5=11 
// 输入大小的扫描，而典型的一级执行16次扫描。
// 
// 线性扫描的成本远不及
// 在一些
// 扫描过程中对文本的随机访问（特别是上面标记的#6、#9、#16、#19、#22）。
// 在真实文本中，由于文本
// （与Burrows-Wheeler压缩非常有效的原因相同）的重复结构，访问除了局部性之外没有太多。
// 对于随机输入，没有局部性，这使得那些
// 访问更加昂贵，尤其是当文本
// 不再适合缓存时。例如，在50MB的Go源代码上运行时，InquiredSubl_8_32 
// （在递归的顶层只运行一次）
// 需要0.44s，而在50MB的随机输入上，需要2.55s。
// 几乎所有的相对减速都是通过文本访问来解释的：
// 
// c0，c1:=文本[k-1]，文本[k]
// 
// 该行在移动文本上运行0.23秒，在随机文本上运行2.02秒。

// go:generate go run gen.go 

package suffixarray

// text_32返回输入文本的后缀数组。
// 它要求len（text）适合int32 
// 并且调用者为零sa。
func text_32(text []byte, sa []int32) {
	if int(int32(len(text))) != len(text) || len(text) != len(sa) {
		panic("suffixarray: misuse of text_32")
	}
	sais_8_32(text, 256, sa, make([]int32, 2*256))
}

// sais_8_32计算文本的后缀数组。
// 文本必须只包含[0，textMax]中的值。
// 后缀数组存储在sa中，调用者
// 必须确保已将其归零。
// 调用者还必须提供临时空间tmp 
// 和len（tmp）≥ textMax.If len（tmp）≥ 2*textMax 
// 那么算法运行得更快一些。
// 如果sais_8_32修改tmp，则设置tmp[0]=-1返回。
func sais_8_32(text []byte, textMax int, sa, tmp []int32) {
	if len(sa) != len(text) || len(tmp) < int(textMax) {
		panic("suffixarray: misuse of sais_8_32")
	}

	// 基本情况很简单。排序0或1很容易。
	if len(text) == 0 {
		return
	}
	if len(text) == 1 {
		sa[0] = 0
		return
	}

	// 建立由文本字符索引的切片
	// 保留字符频率和桶排序偏移量。
	// 如果一个切片只有足够的tmp，
	// 我们将其设置为桶偏移量和重新计算
	// 每次需要时的字符频率。
	var freq, bucket []int32
	if len(tmp) >= 2*textMax {
		freq, bucket = tmp[:textMax], tmp[textMax:2*textMax]
		freq[0] = -1 // 标记为未初始化
	} else {
		freq, bucket = nil, tmp[:textMax]
	}

	// SAIS算法。
	// 这些调用中的每一个都通过sa进行一次扫描。
	// 有关每个调用在算法.
	numLMS := placeLMS_8_32(text, sa, freq, bucket)
	if numLMS <= 1 {
		// 0或1项已排序。不执行任何操作。
	} else {
		induceSubL_8_32(text, sa, freq, bucket)
		induceSubS_8_32(text, sa, freq, bucket)
		length_8_32(text, sa, numLMS)
		maxID := assignID_8_32(text, sa, numLMS)
		if maxID < numLMS {
			map_32(sa, numLMS)
			recurse_32(sa, tmp, numLMS, maxID)
			unmap_8_32(text, sa, numLMS)
		} else {
			// 如果maxID==numls，则每个LMS子字符串
			// 是唯一的，因此两个LMS后缀
			// 的相对顺序仅由前导的LMS子字符串确定。
			// 即LMS后缀排序顺序r匹配
			// （更简单）LMS子字符串排序顺序。
			// 将原始LMS子字符串顺序复制到
			// 后缀数组目标中。
			copy(sa, sa[len(sa)-numLMS:])
		}
		expand_8_32(text, freq, bucket, sa, numLMS)
	}
	induceL_8_32(text, sa, freq, bucket)
	induceS_8_32(text, sa, freq, bucket)

	// 为调用方标记我们重写了tmp。
	tmp[0] = -1
}

// freq_8_32返回文本的字符频率
// 作为按字符值索引的片段。
// 如果freq为零，freq_8_32使用并返回bucket.
// 如果freq为非零，freq_8_32假设freq[0]>=0 
// 表示已经计算了频率。
// 如果频率数据被覆盖或未初始化，
// 调用者必须设置freq[0]=-1强制重新计算
// 下次需要时。
func freq_8_32(text []byte, freq, bucket []int32) []int32 {
	if freq != nil && freq[0] >= 0 {
		return freq // 已计算
	}
	if freq == nil {
		freq = bucket
	}

	freq = freq[:256] // 消除
	for i := range freq {
		freq[i] = 0
	}
	for _, c := range text {
		freq[c]++
	}
	return freq
}

// 以下频率[c]的边界检查BACKETMIN_8_32存储到bucket[c]bucket排序文本中字符c在bucket中的最小索引
// 
func bucketMin_8_32(text []byte, freq, bucket []int32) {
	freq = freq_8_32(text, freq, bucket)
	freq = freq[:256]     // 建立len（freq）=256，所以0≤ i<256以下
	bucket = bucket[:256] // 消除对bucket的边界检查[i]
	total := int32(0)
	for i, n := range freq {
		bucket[i] = total
		total += n
	}
}

// bucketMax_8_32将最大索引
// 存储在bucket中，用于bucket排序文本中的字符c。
// c的bucket索引为[min，max.
// 也就是说，max超过了该存储桶中的最终索引。
func bucketMax_8_32(text []byte, freq, bucket []int32) {
	freq = freq_8_32(text, freq, bucket)
	freq = freq[:256]     // 建立len（freq）=256，所以0≤ i<256低于
	bucket = bucket[:256] // 消除桶的边界检查[i]低于
	total := int32(0)
	for i, n := range freq {
		total += n
		bucket[i] = total
	}
}

// SAIS算法通过sa进行一系列扫描。
// 以下每个函数实现一次扫描，
// 并且这些函数按照它们在算法中执行的顺序显示在这里。

// placeLMS_8_32将文本的LMS子字符串的最终字符
// 的索引放入sa中，
// 排序到其正确存储桶的最右端
// 在后缀数组中。
// 
// 文本末尾的假想哨兵字符
// 是最终LMS子字符串的最终字符，但没有用于假想哨兵字符
// 的存储桶，其值小于任何实数字符。
// 因此，调用方必须假装sa[-1]==len（text）。
// 
// LMS子字符串字符的文本索引始终为≥ 1 
// （第一个LMS子字符串前面必须有一个或多个不属于任何LMS子字符串的L型
// 字符），
// 因此使用0作为“不存在”后缀数组项是安全的，
// 在本函数和大多数后续函数中都是如此.ABCFDG＊＊＊＊＊＊＊＊/ABCDEG＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊？是一个S字符。也就是说，i+1是LMS子字符串的起始位置。这些可以通过回调提升到一个函数中，但速度代价非常大。相反，我们只需在这个源文件中编写这些
func placeLMS_8_32(text []byte, sa, freq, bucket []int32) int {
	bucketMax_8_32(text, freq, bucket)

	numLMS := 0
	lastB := int32(-1)

	// 七行。副本下面，请回到原作中建立的模式，即
	// “LMS子字符串迭代器”。
	// 
	// 在通过文本的每次扫描中，c0、c1是文本的连续字符。
	// 在这次反向扫描中，c0==text[i]和c1==text[i+1].
	// 通过向后扫描，我们可以跟踪当前
	// 位置是类型-S还是类型-L，根据通常的定义：
	// 
	// /-位置len（text）是类型S，带有文本[len（text）]=-1（哨兵）
	// /-位置i是类型S，如果文本[i]<text[i+1]，或如果text[i]==text[i+1]&&i+1为S型。如果text[i]>text[i+1]，或如果text[i]==text[i+1]，则位置i为L型&&i+1是类型L。
	// 
	// 反向扫描允许我们保持当前类型，
	// 当我们看到c0！=c1时更新它，否则就不使用它。
	// 我们想用前面的L标识所有S位置。
	// 位置len（文本）根据定义就是这样一个位置，但是我们没有地方写它，所以我们通过在循环开始时不真实地设置isTypeS=false来消除它ly想要结束。
	c0, c1, isTypeS := byte(0), byte(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			b := bucket[c1] - 1
			bucket[c1] = b
			sa[b] = int32(i + 1)
			lastB = b
			numLMS++
		}
	}

	// 幸运的是，有两个不同之处，开始索引和结束索引是相同的。
	// 第一个不同之处是最右边的LMS子字符串的结束索引是len（text），
	// 因此调用方必须假装sa[-1]==len（text），如上所述。
	// 第二个区别是，第一个最左边的LMS子字符串开始索引
	// 不结束较早的LMS子字符串，因此作为优化，我们可以省略最左边的LMS子字符串开始索引（我们编写的最后一个）.
	// 
	// 异常：如果numms<=1，调用方根本不需要处理
	// 递归将视结果为包含LMS子字符串启动。
	// 在这种情况下，我们不删除最终条目。
	if numLMS > 1 {
		sa[lastB] = 0
	}
	return numLMS
}

// induceSubL_8_32插入L-type文本indLMS子字符串
// 的EXE插入sa，假设LMS子字符串
// 的最终字符已插入sa，按最终字符排序，并位于相应字符桶的
// 右（非左）端。
// 每个LMS子字符串的形式（作为regexp）/S+L+S/：
// 一个或多个S型、一个或多个L型、最终S型。
// INDUCTSUBL_8_32只为每个LMS子字符串留下最左边的L型文本
// 索引。也就是说，它删除条目上存在的最终S型
// 索引，然后插入但删除
// 内部的L型索引也是。
// （InquiredSubs_8_32只需要最左边的L型索引）
func induceSubL_8_32(text []byte, sa, freq, bucket []int32) {
	// 初始化字符桶左侧的位置。
	bucketMin_8_32(text, freq, bucket)
	bucket = bucket[:256] // 取消对

	// 下面的bucket[cB]的边界检查
	// 当我们从左到右扫描数组时，每个sa[i]=j>0都是正确的
	// 排序后缀数组项（对于文本[j:]），我们知道j-1的类型是L。
	// 因为j-1是L类型，现在将其插入sa将正确排序。
	// 但是我们想区分类型为L和类型为S的j-1和j-2。
	// 我们可以处理前者，但希望将后者留给调用方。
	// 如果j-1前面有类型S，则通过对其求反来记录差异。
	// 无论哪种方式，插入（到文本[j-1]bucket中）都保证对某些i'>i在sa[i']发生，也就是说，在sa的部分，我们还有
	// 要扫描。因此，单次传递将以排序但不一定相邻的顺序看到索引j、j-1、j-2、j-3、
	// 等等，直到它找到前面有一个S类型索引的索引，此时它必须停止。
	// 
	// 当我们扫描数组时，我们将工作项（sa[i]>0）清除为零，
	// 并将sa[i]<0翻转为-sa[i]，这样循环结束时，sa包含
	// 每个LMS子字符串的最左侧L型索引的索引。
	// 
	// 因此，后缀数组sa同时充当输入、输出、
	// 和一个精心定制的工作队列。

	// placeLMS_8_32遗漏了隐式条目sa[-1]==len（text），
	// 对应于标识的type-L索引len（text）-1。
	// 在sa正确从左向右扫描之前进行处理。
	// 有关评论，请参见循环正文。
	k := len(text) - 1
	c0, c1 := text[k-1], text[k]
	if c0 < c1 {
		k = -k
	}

	// 缓存最近使用的bucket index:
	// 我们正在按排序顺序处理后缀
	// 并访问排序顺序前由
	// 字节索引的bucket，这仍然是
	// 具有很好的局部性。
	// 不变量：b已缓存，可能是bucket[cB]的脏副本。
	cB := c1
	b := bucket[cB]
	sa[b] = int32(k)
	b++

	for i := 0; i < len(sa); i++ {
		j := int(sa[i])
		if j == 0 {
			// 跳过空条目。
			continue
		}
		if j < 0 {
			// 为调用者保留发现的S型索引。
			sa[i] = int32(-j)
			continue
		}
		sa[i] = 0

		// 索引j在工作队列上，这意味着k:=j-1是L型，
		// 所以我们现在可以将k正确地放入sa中。
		// 如果k-1是L-type，则将k排队，以便稍后在此循环中处理。
		// 如果k-1是S-type（text[k-1]<text[k]），则将-k队列保存给调用者。
		k := j - 1
		c0, c1 := text[k-1], text[k]
		if c0 < c1 {
			k = -k
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		sa[b] = int32(k)
		b++
	}
}

// INDUCTSUB_8_32将LMS子字符串
// 的S型文本索引插入sa，假设最左边的L型文本索引已经是
// 插入sa，按LMS子字符串后缀排序，并位于相应字符桶的
// 左端。
// 每个LMS子字符串的形式为（作为regexp）/S+L+S/：
// 一个或多个S型、一个或多个L型、最终S型。
// INDUCTSUB_8_32只在sa的右端按排序顺序为每个LMS子字符串留下最左边的S型文本
// 索引。
// 也就是说，它删除条目中存在的L型索引，
// 并插入但随后删除内部S型索引，
// 将LMS子字符串开始索引打包到sa[len（sa）-numLMS:]。
// （递归只处理LMS子字符串开始索引。）
func induceSubS_8_32(text []byte, sa, freq, bucket []int32) {
	// 初始化字符桶右侧的位置。
	bucketMax_8_32(text, freq, bucket)
	bucket = bucket[:256] // 消除对

	// 下面的bucket[cB]的边界检查类似于上面的inquiredSubl_8_32，
	// 当我们从右向左扫描数组时，每个sa[i]=j>0都是正确的
	// 排序的后缀数组项（对于文本[j:]）我们知道j-1是S类型。
	// 因为j-1是S类型，现在将其插入sa将正确排序。
	// 但是我们想区分类型为S和类型为L的j-1和j-2。
	// 我们可以处理前者，但希望将后者留给调用方。
	// 如果在j-1前面加上类型L，我们通过对其求反来记录差异。
	// 无论哪种方式，插入（到文本[j-1]bucket中）都保证对某些i´<i在sa[i´发生，也就是说，在sa的部分，我们还有
	// 要扫描。因此，单次传递可以看到索引j、j-1、j-2、j-3、
	// 等等，按排序但不一定是相邻的顺序，直到找到
	// 前面有一个L类型的索引，在该索引处必须停止。
	// 该索引（前面有一个类型为L的索引）是LMS子字符串的开始。
	// 
	// 当我们扫描数组时，我们将工作项（sa[i]>0）清除为零，
	// 然后将sa[i]<0翻转为-sa[i]，并压缩到sa的顶部，
	// 这样循环结束时，sa的顶部正好包含
	// LMS子字符串开始索引，按LMS子字符串排序。

	// 缓存最近使用的bucket索引：
	cB := byte(0)
	b := bucket[cB]

	top := len(sa)
	for i := len(sa) - 1; i >= 0; i-- {
		j := int(sa[i])
		if j == 0 {
			// 跳过空条目。
			continue
		}
		sa[i] = 0
		if j < 0 {
			// 为调用者保留发现的LMS子字符串开始索引。
			top--
			sa[top] = int32(-j)
			continue
		}

		// 索引j在工作队列上，这意味着k:=j-1是S型，
		// 因此我们现在可以将k正确地放入sa中。
		// 如果k-1是S-type，则将k排入队列以便稍后在此循环中处理。
		// 如果k-1是L-type（text[k-1]>text[k]），则将-k队列保存给调用者。
		k := j - 1
		c1 := text[k]
		c0 := text[k-1]
		if c0 > c1 {
			k = -k
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		b--
		sa[b] = int32(k)
	}
}

// length_8_32计算并记录文本中每个LMS子字符串的长度。
// 索引j处的LMS子字符串长度存储在sa[j/2]，
// 避免存储在sa上半部分的LMS子字符串索引。
// （如果索引j是LMS子字符串开始，那么索引j-1是L类型，不能是。）
// 有两个例外，用于下面名称_8_32中的优化。
// 
// 首先，最后的LMS子字符串被记录为长度为0，否则
// 不可能，而不是给它一个包含隐式哨兵的长度。
// 这确保了最终LMS子串的长度不等于所有其他子串
// 因此可以在不进行文本比较的情况下检测为不同
// （这是不平等的，因为它是以隐式哨兵
// 结尾的唯一一个，文本比较会有问题，因为隐式哨兵
// 实际上不存在于文本[len（text）]）.
// 
// 其次，为了完全避免文本比较，如果LMS子字符串非常短，
// sa[j/2]记录其实际文本而不是其长度，因此如果两个这样的
// 子字符串具有匹配的“长度”，则根本不需要读取文本。
// “极短”是指文本字节必须打包到uint32、
// 中，且无符号编码e必须为≥ len（text），因此它可以是
// 与有效长度区分。
func length_8_32(text []byte, sa []int32, numLMS int) {
	end := 0 // 当前LMS子字符串结束的索引（0表示最终LMS子字符串）

	// 将N个文本字节编码为“长度”单词
	// 每个字节加1，将它们压缩到单词的底部
	// N*8位，然后按位反转结果。
	// 也就是说，文本序列a B C（十六进制41 42 43）
	// 编码为^uint32（0x42_43_44）.
	// LMS子字符串永远不能以0xFF开头或结尾。
	// 添加1可确保编码的字节序列永远不会以0x00开头或结尾
	// 因此当前字节可以是
	// 区别于顶部位中的零填充，
	// 因此长度不需要分开y编码。
	// 反转字节会增加
	// 仍然使用4字节编码的可能性≥ len（text）.
	// 特别是，如果第一个字节是ASCII（<=0x7E，所以+1<=0x7F）
	// 那么将设置反转的高位，使其明显不是有效长度（它将是负的）。
	// 
	// cx保留预反转编码（填充的增量字节）.abcDef

	// 如上所述，添加一行以维护cx。
	c0, c1, isTypeS := byte(0), byte(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		cx = cx<<8 | uint32(c1+1) // 仅字节
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// 索引j=i+1是LMS子字符串的开始。
			// 计算要存储在sa中的长度或编码文本[j/2].
			j := i + 1
			var code int32
			if end == 0 {
				code = 0
			} else {
				code = int32(end - j)
				if code <= 32/8 && ^cx >= uint32(len(text)) { // 仅字节
					code = int32(^cx) // 仅字节
				} // 仅字节
			}
			sa[j>>1] = code
			end = j + 1
			cx = uint32(c1 + 1) // 仅字节
		}
	}
}

// assignID_8_32为
// 关于字符串顺序和相等性的LMS子字符串集分配密集的ID编号，
// 返回分配的最大ID。
// 例如，给定输入“ababab”，LMS子字符串
// 是“aba”、“aba”和“ab”，重新编号为2 2 1。
// sa[len（sa）-numLMS:]保存按字符串顺序排序的LMS子字符串索引
// 以便分配数字
// 索引j处LMS子字符串的新ID被写入sa[j/2]，
// 覆盖先前存储在那里的长度（按上面的长度_8_32）。
func assignID_8_32(text []byte, sa []int32, numLMS int) int {
	id := 0
	lastLen := int32(-1) // 不可能
	lastPos := int32(0)
	for _, j := range sa[len(sa)-numLMS:] {
		// 索引j处的LMS子字符串是新的，还是与我们上次看到的相同？
		n := sa[j/2]
		if n != lastLen {
			goto New
		}
		if uint32(n) >= uint32(len(text)) {
			// /“Length”实际上是全文编码的，它们匹配。
			goto Same
		}
		{
			// 比较实际文本。
			n := int(n)
			this := text[j:][:n]
			last := text[lastPos:][:n]
			for i := 0; i < n; i++ {
				if this[i] != last[i] {
					goto New
				}
			}
			goto Same
		}
	New:
		id++
		lastPos = j
		lastLen = n
	Same:
		sa[j/2] = int32(id)
	}
	return id
}

// map_32将文本中的LMS子字符串映射到它们的新ID，
// 为递归生成子问题。
// 映射本身主要由assignID_8_32应用：
// sa[i]为0、索引2*i处LMS子字符串的ID、
// 或索引2*i+1处LMS子字符串的ID。
// 要生成子问题，我们只需删除零
// 并将ID更改为ID-1（我们的ID从1开始，但文本字符从0开始）。
// 
// map_32将作为递归输入的结果
// 打包到sa的顶部，以便将递归结果存储在sa的底部，这为扩展_8_32做好了准备。
func map_32(sa []int32, numLMS int) {
	w := len(sa)
	for i := len(sa) / 2; i >= 0; i-- {
		j := sa[i]
		if j > 0 {
			w--
			sa[w] = j - 1
		}
	}
}

// recurse_32递归调用sais_32来解决我们构建的子问题。
// 子问题在sa的右端，后缀数组结果将是
// 写入sa的左端，sa的中间可用作
// 临时频率和存储桶。
func recurse_32(sa, oldTmp []int32, numLMS, maxID int) {
	dst, saTmp, text := sa[:numLMS], sa[numLMS:len(sa)-numLMS], sa[len(sa)-numLMS:]

	// 为递归调用设置临时空间。
	// 我们必须向sais_32传递一个tmp缓冲区，该缓冲区至少包含maxID条目。
	// 
	// 保证子问题的长度不超过len（sa）/2，
	// 以便sa可以同时容纳子问题及其后缀数组。
	// 然而，几乎所有的时候，子问题的长度都小于len（sa）/3，
	// 在这种情况下，有一个子问题大小在sa中间，
	// 我们可以重用为临时空间（saTmp）。
	// 当从sais_8_32调用recurse_32时，oldTmp的长度为512 
	// （从text_32），而saTmp通常要大得多，因此我们将使用saTmp。
	// 当更深的递归返回到递归时，现在oldTmp是
	// 从最上面的递归开始的saTmp，它通常比
	// 当前的saTmp大（因为当前sa随着递归的加深而变得越来越小），我们继续使用最顶级的
	// 大型saTmp，而不是提供的小型saTmp。
	// 
	// 为什么子问题的长度经常小于len（sa）/3？
	// 有关合理的解释，请参见农、张和陈，第3.6节。简而言之，len（sa）/2案例将对应于输入中的SLSL模式
	// 大小输入字节的完美交替。
	// Real text不会这样做。如果每个L-type索引后面随机跟随一个L-type或S-type索引，则一半子字符串的形式为SLS，但另一半较长。其中，
	// 一半（总的四分之一）将是SLL；第八个是SLLL，以此类推。
	// 不计算每一个中的最后一个S（与下一个中的第一个S重叠），
	// 计算出的平均长度为2×½+3×¼+4×2⅛ + ... = 3.
	// 我们需要的空间进一步减少，因为许多像SLS这样的短模式通常是相同的字符序列，在整个文本中重复，从而减少了相对于numms的maxID。
	// 
	// 对于短输入，平均值可能不利于我们，但我们
	// 通常可以使用
	// 最顶端调用中可用的长度为512的tmp。（同样，短分配也不是什么大问题。）对于病理输入，我们返回到分配长度为
	// max（maxID，numls/2）的新tmp。这个级别的递归需要maxID，
	// 并且所有更深级别的递归都不需要超过numms/2，
	// 所以这个分配保证足以满足整个堆栈
	// 的递归调用。
	tmp := oldTmp
	if len(tmp) < len(saTmp) {
		tmp = saTmp
	}
	if len(tmp) < numLMS {
		// TestSAIS/forcealloc到达此代码。
		n := maxID
		if n < numLMS/2 {
			n = numLMS / 2
		}
		tmp = make([]int32, n)
	}

	// sais_32要求调用者安排清除dst，
	// 因为通常调用者可能知道dst是
	// 新分配且已清除。但这个不是。
	for i := range dst {
		dst[i] = 0
	}
	sais_32(text, maxID, dst, tmp)
}

// 取消映射_8_32将子问题取消映射回原始问题。
// sa[:numLMS]是LMS子字符串的编号，它们不再重要。
// sa[len（sa）-numLMS:]是这些LMS子字符串编号的排序列表。
// 关键部分是，如果列表中显示K，则表示第K个子字符串。
// 我们可以用LMS子字符串的索引替换sa[：numls]。
// 那么如果列表上写的是K，那么它实际上意味着sa[K]。
// 将列表映射回LMS子字符串索引后，
// 我们可以将它们放入正确的存储桶中。
func unmap_8_32(text []byte, sa []int32, numLMS int) {
	unmap := sa[len(sa)-numLMS:]
	j := len(unmap)

	// /“LMS子串迭代器”（见上文第8部分第32节）。
	c0, c1, isTypeS := byte(0), byte(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// 填充反向映射。
			j--
			unmap[j] = int32(i + 1)
		}
	}

	// 对子问题后缀数组应用逆映射。
	sa = sa[:numLMS]
	for i := 0; i < len(sa); i++ {
		sa[i] = unmap[sa[i]]
	}
}

// expand_8_32将压缩、排序的LMS后缀索引
// 从sa[：numms]分配到sa中相应桶的顶部，
// 保留排序顺序，并为L型索引
// 留出空间，以便通过INDUL_8_32将其插入排序序列。
func expand_8_32(text []byte, freq, bucket, sa []int32, numLMS int) {
	bucketMax_8_32(text, freq, bucket)
	bucket = bucket[:256] // 消除对

	// 下面的bucket[c]的绑定检查，通过sa向后循环，始终跟踪
	// 从sa填充的下一个索引[：numls]。
	// 当我们找到一个时，填充它。
	// 将剩余插槽归零；他们有死的价值。
	x := numLMS - 1
	saX := sa[x]
	c := text[saX]
	b := bucket[c] - 1
	bucket[c] = b

	for i := len(sa) - 1; i >= 0; i-- {
		if i != int(b) {
			sa[i] = 0
			continue
		}
		sa[i] = saX

		// 加载下一个要放下的条目（如果有）。
		if x > 0 {
			x--
			saX = sa[x] // TODO bounds check 
			c = text[saX]
			b = bucket[c] - 1
			bucket[c] = b
		}
	}
}

// INDUCTL_8_32将L型文本索引插入sa，
// 假设最左边的S型索引按排序顺序插入sa的右半桶中。
// 将所有L型索引保留在sa中，但将最左侧的L型索引取反，以将其标记为
// 以便通过归纳法进行处理。
func induceL_8_32(text []byte, sa, freq, bucket []int32) {
	// 初始化字符桶左侧的位置。
	bucketMin_8_32(text, freq, bucket)
	bucket = bucket[:256] // 消除低于

	// 的桶[cB]的边界检查此扫描与上面的INDUCTSUB_8_32中的扫描类似。
	// 除最左边的L型索引外，安排清除所有索引。
	// 此扫描将保留所有L型索引和原始S型
	// 索引，但它将否定最左侧的正L型索引
	// （导致_8_32的索引需要处理）。

	// expand_8_32省略了隐式条目sa[-1]==len（text），
	// 对应于标识的type-L索引len（text）-1。
	// 在sa正确从左向右扫描之前进行处理。
	// 有关评论，请参见循环正文。
	k := len(text) - 1
	c0, c1 := text[k-1], text[k]
	if c0 < c1 {
		k = -k
	}

	// 缓存最近使用的bucket索引。
	cB := c1
	b := bucket[cB]
	sa[b] = int32(k)
	b++

	for i := 0; i < len(sa); i++ {
		j := int(sa[i])
		if j <= 0 {
			// 跳过空的或否定的条目（包括否定的零）。
			continue
		}

		// 索引j在工作队列上，这意味着k:=j-1是L型，
		// 所以我们现在可以将k正确地放入sa中。
		// 如果k-1是L-type，则将k排队，以便稍后在此循环中处理。
		// 如果k-1是S-type（text[k-1]<text[k]），则队列-k为调用者保存。
		// 如果k为零，则k-1不存在，因此我们只需将其留给调用者
		// 即可。调用方无法区分
		// 空插槽和非空零之间的区别，但无论如何也不需要
		// 来区分它们：最后的后缀数组将以
		// 结尾，在某个地方有一个零，这将是一个真正的零。
		k := j - 1
		c1 := text[k]
		if k > 0 {
			if c0 := text[k-1]; c0 < c1 {
				k = -k
			}
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		sa[b] = int32(k)
		b++
	}
}

func induceS_8_32(text []byte, sa, freq, bucket []int32) {
	// 初始化字符桶右侧的位置。
	bucketMax_8_32(text, freq, bucket)
	bucket = bucket[:256] // 消除桶[cB]在

	cB := byte(0)
	b := bucket[cB]

	for i := len(sa) - 1; i >= 0; i-- {
		j := int(sa[i])
		if j >= 0 {
			// 下面的边界检查跳过未标记的条目。
			// （此循环无法看到空条目；0表示实际零索引。）
			continue
		}

		// /负j是工作队列条目；将最终后缀数组重写为正j。
		j = -j
		sa[i] = int32(j)

		// 索引j在工作队列上（编码为-j，但现在已解码），
		// 意思是k:=j-1是L型，
		// 因此我们现在可以将k正确地放入sa中。
		// 如果k-1是S-type，则将-k排队，以便稍后在此循环中处理。
		// 如果k-1是L-type（text[k-1]>text[k]），则将k排队以保存给调用者。
		// 如果k为零，则k-1不存在，因此我们只需将其留给调用者
		// 即可。
		k := j - 1
		c1 := text[k]
		if k > 0 {
			if c0 := text[k-1]; c0 <= c1 {
				k = -k
			}
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		b--
		sa[b] = int32(k)
	}
}
